The present invention relates to addition circuits for adding a binary number A to a binary number B, and more particularly but not exclusively to addition circuits designed to meet particular process or application criteria.
A variety of different addition circuits are known. One basic example is illustrated in FIG. 1. The binary number A is represented as a series of bits ai where i is the binary weight of the bit ai and increases from the value zero for the least significant bit of A in steps of one to the value of the most significant bit of A. The binary number B is a series of bits bi where i is the binary weight of the bit. The summation of the numbers A and B is represented by the binary number S which is a series of bits si where i is the binary weight of the bit, and C8 which is the msb of the sum.
The bit a0 and the bit b0 are supplied as inputs to an AND gate 20 which produces the bit generate g0. The bit a0 and the bit b0 are also supplied as inputs to an XOR gate 40 which produces s0 as its output. The bit a1 and the bit b1 are supplied as inputs to an XOR gate 41 which produces the first bit propagate signal p1. The bit generate signal g0 and the first bit propagate signal p1 are supplied as inputs to an XOR gate 241 which produces the bit s1. The bit a1 and the bit b1 are also supplied as inputs to an OR gate 61 which supplies its output as a first input to an AND gate 81. The second input of the AND gate 81 is received from the output of the AND gate 20. The output of the AND gate 81 provides a first input to an OR gate 101. The second input to the OR gate 101 is received from an AND gate 21 which receives as inputs the bit a1 and the bit b1. The bit a2 and the bit b2 are supplied as inputs to an XOR gate 42 which provides its output as a first input to a XOR gate 242. The second input to the XOR gate 242 is provided by the output of the OR gate 101. The output of the XOR gate 242 provides the bit s2. The bit a2 and the bit b2 are also combined in an OR gate 62 to produce a first input to an AND gate 82 which receives as a second input the output from the OR gate 101.
The output from the AND gate 82 supplied as a first input to a OR gate 102. The second input to the OR gate 102 is supplied by a AND gate 22 which receives as an input the bits a2 and b2. The output of the OR gate 102 is supplied as a first input to a XOR gate 243. The second input to the XOR gate 243 is supplied by the output of an XOR gate 43 which receives as inputs the bit a3 and the bit b3. The output of the XOR gate 243 provides the bit s3. An AND gate 23 also receives the bits a3 and b3 and provides its output as a first input to a OR gate 163. The second input to the OR gate 163 is provided by an AND gate 143 which receives as a first input the output from the AND gate 22 and as a second input the output from an OR gate 63 which receives as inputs the bit a3 and bit b3. The output from the OR gate 63 is also provided as a first input to an AND gate 123 which receives as a second input the output from the OR gate 62.
The output from the AND gate 123 is supplied as a first input to an AND gate 83 which receives as a second input the output from the OR gate 101. The output from the AND gate 83 and the output from the OR gate 163 are combined in an OR gate 103. A XOR gate 244 receives as a first input the output from the OR gate 103 and as a second input the output from an XOR gate 44 which receives as inputs the bit a4 and the bit b4. The XOR gate 244 produces the bit s4.
An OR gate 64 receives an inputs the bit a4 and bit b4 and provides its output as a first input to an AND gate 84. The AND gate 84 receives as its second input the output from the OR gate 103 and provides its output to a OR gate 104. The other input to the OR gate 104 is provided by an AND gate 24 which receives as inputs the bit a4 and the bit b4. An XOR gate 245 produces the bit s5 and receives as a first input the output from the OR gate 104 and receives as a second input the output from an XOR gate 45 which receives as inputs the bit as and the bit b5. An AND gate 125 receives as a first input the output from the OR gate 64 and an output from an OR gate 65 which receives as inputs the bit a5 and the bit b5.
An OR gate 165 receives as a first input the output from an AND gate 25 which receives as inputs the bit as and the bit b5 and as a second input receives the output from an AND gate 145 which itself receives as inputs the output from the AND gate 24 and the output from the OR gate 65. The output from the AND gate 125 is combined with the output from the OR gate 103 in an AND gate 85 to produce a first input to a first OR gate 105. The second input to the OR gate 105 is provided by the output from the OR gate 165.
The output from the OR gate 105 is provided as a first input to the XOR gate 246. The XOR gate 246 receives as a second input the output from the XOR gate 46 which receives as inputs the bit a6 and the bit b6. The XOR gate 246 produces as an output the bit s6.
An OR gate 66 receives as its inputs the bit a6 and the bit b6 and supplies its output as a first input to an AND gate 126. The second input to the AND gate 126 is supplied by the output of the AND gate 125 and the output of the AND gate 126 is supplied as a first input to an AND gate 86.
The output from the OR gate 66 is supplied as a first input to an AND gate 146. The AND gate 146 receives as a second input the output from the OR gate 165 and provides an output signal to a first input of an OR gate 166. The second input to the OR gate 166 is supplied by an AND gate 26 which receives as inputs the bit a6 and the bit b6. The AND gate 86 which receives as a first input the output from the AND gate 126 receives as a second input the output from the OR gate 103 and provides its output as a first input to an OR gate 106. The second input to the OR gate 106 is provided by the output of the OR gate 166.
The output of the OR gate 106 is provided as a first input to an XOR gate 247. The XOR gate 247 receives as a second input the output from an XOR gate 47 which receives as inputs the bit a7 and the bit b7. The XOR gate 247 produces the bit s7.
The bit a7 and the bit b7 are combined in an OR gate 67 to produce a first input to an AND gate 187 which receives as a second input the output from the OR gate 66. The output from the OR gate 67 is supplied as a first input to an AND gate 207. The AND gate 207 receives as a second input the output from the AND gate 26. The output from the AND gate 207 is supplied as a first input to an OR gate 227. The second input to the OR gate 227 is provided by a AND gate 27 which receives as its inputs the bit signal a, and the bit signal b7.
An AND gate 147 receives as its inputs the output from the AND gate 187 and the output from the OR gate 165 and provides its output as a first input to an OR gate 167. The second input to the OR gate 167 is supplied by the output of the OR gate 227. The output of the OR gate 167 is provided as a first input to an OR gate 107. An AND gate 127 receives as its inputs the output from the AND gate 127 and the output from the AND gate 187. The output from the AND gate 127 is supplied as a first input to the AND gate 87. The AND gate 87 receives as a second input the output from the OR gate 103. The output from the AND gate 87 is supplied as a second input to the OR gate 107. The output of the OR gate 107 produces the last carry value c8.
An addition circuit that can quickly change between producing an output value A+B and output value A+B+1 or that can simultaneously provide an output value A+B and an output value A+B+1 is described in an earlier GB patent application No. 9813328.3.
The addition circuitry described in that application has a plurality of addition paths, with each addition path having inputs for receiving respectively bits ai, bi of the first and second binary numbers and output means for producing respectively bits si, sxe2x80x2i of third (A+B) and fourth (A+B+1) binary numbers.
By modification to the output means, the circuit can be configured to provide a number of different useful outputs, such as A+B or A+B+1; A+B and A+B+1; Axe2x88x92B and Bxe2x88x92A; Axe2x88x92B or Bxe2x88x92A; and modulus Axe2x88x92B. Thus, the circuit has a number of different useful applications.
Each addition path has a number of logical nodes in the depth direction of the circuit (input to output). Each set of nodes arranged widthwise of the circuit (that is in the direction of bit significance) forms a logical stage. Each adjacent pair of addition paths defines a column. An addition circuit of so-called xe2x80x9cminimum depthxe2x80x9d has the minimum number of logical stages which are required to add together the binary numbers according to their length n. Clearly, the greater the length n of binary numbers to be added, the higher is the number of stages even in a xe2x80x9cminimum depthxe2x80x9d circuit.
In developing a minimum depth circuit, clearly constraints are imposed on how the logical nodes can be interconnected. In GB Application No. 9813328.3, the circuit is designed so that each logical node is connected to as many logical nodes in the subsequent logical stage as possible. This connection is made via the addition path for the node and by one or more spanning path which crosses at least one column. The number of nodes in a subsequent stage to which a node of the preceding logical stage is connected by spanning paths is termed herein xe2x80x9cfan-outxe2x80x9d.
Thus, the circuit of the earlier application is designed with so-called maximum fan-out. This has the advantage of minimising the number of wires that are required to make the circuit, but has the disadvantage that delays between logical states are incurred as a result of the capacitance introduced by the large number of gates connected to particular wires, particularly in the later logical stages.
Another possibility is to interconnect a node of a logical stage to a unique single node of a subsequent stage, which has the advantage of reducing fan-out (to a fan-out of 1), but the disadvantage of requiring a large number of wires which increases the space requirement for the circuit.
It is desirable to be able to design an addition circuit to accommodate a number of different process and application criteria. In particular, it is desirable to facilitate the process of designing an addition circuit of minimum depth.
According to the invention there is provided an addition circuit for adding together two operands, for example, two binary numbers (A,B), each having a length of n bits. The circuit includes an array of logical nodes that are arranged so that each set of logical nodes extending widthwise of the circuit form a logical stage and each set of nodes extending depthwise of the circuits form an addition path, with each pair of adjacent addition paths forming a column. Spanning paths are arranged to interconnect selected logical nodes so that adjacent logical stages are connected via an interconnection level, each spanning path extending from a node in one stage across at least one column and being connected to a number f of fan-out nodes in a subsequent stage.
The circuit has one or more of the following configuration parameters:
i) for each interconnection level the number f of fan-out nodes lies in the range 1 to 2j, where j is the interconnection level index lying between 0 and m, 2j is the maximum fan-out number for that level, and there are m+2 logical stages;
ii) the fan-out f of nodes at each level is always no greater than the number f of fan-out nodes at a subsequent level;
iii) the number of columns across which a spanning path extends within an interconnection level is 2j; and
at least one level has a fan-out number f less than 2j and at least one level has a fan-out number f greater than 1.
By defining a number of criteria for the addition circuit in terms of the configuration parameters referred to above, it is possible to design the addition circuit to suit the particular requirements at hand. That is, it allows designs to be constructed with fewer spanning wires and/or lower fan-out without significantly compromising speed requirements for a given circuit depth. The configuration parameters allow a number of design trade-offs to be considered each time resulting in an optimized addition circuit for the particular instant application.
The invention is particularly useful in the context of minimum depth addition circuits. For an addition circuit of minimum depth, the number (m+2) of logical stages is derived from the following equations:
n=2m+1 (where n is a binary order), and
nb0=2m+1 (where n is not a binary order and where nb0 is the next largest binary order after n).
In the described embodiment, each logical node comprises at least one logic gate that receives at least two signals representing bits of the same significance i in the binary numbers a, b to be added.
Each spanning path can convey one or more signals from a node of one significance in one logical stage to a node of a different significance in a subsequent logical stage.
Another aspect of the invention provides a method of designing an addition circuit for adding together two binary numbers (A,B) each of bit length n. The method includes:
determining the number (m+2) of logical stages in the addition circuit according to the following:
for bit length n of a binary order, n=2m+1 and for bit lengths that are not binary orders nb0=2m+1 where nb0 is the next largest binary order after n;
for each of said logical stages allocating a set of virtual nodes, the virtual nodes forming potential addition paths depthwise of the circuit and adjacent addition paths forming a column;
determining for each logical stage its expected input capacitance; and
defining spanning paths wherein the spanning paths constitute an interconnection level between adjacent logical stages, wherein definition of the spanning paths is carried out in accordance with the following configuration parameters and depending on the expected input capacitance of each stage:
i) for each interconnection level the number f of fan-out nodes in a subsequent stage to which a node of a preceding stage is connected lies in the range 1 to 2j, where j is the interconnection level index lying between 0 and m and 2j is the maximum fan-out number for that level,
ii) the fan-out f of nodes at each level is always no greater than the fan-out f of nodes at a subsequent level,
iii) the number of columns across which a spanning path extends within an interconnection level is 2j, and
at least one level has a fan-out number f less than 2j and at least one level has a fan-out number f greater than 1.
A number of different specific examples are possible. By way of illustration, the following particular examples are mentioned, but this is in no way a comprehensive list of all of the possible options.
An addition circuit wherein the fan-out f=1 for more than one level.
An addition circuit wherein f=1 for all levels except the mth level.
An addition circuit wherein at least one level has maximum fan-out f=2 where j is not equal to m.
An addition circuit where the fan-out f=2 for at least two levels.